class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
        tmp = head.next
        head.next = None
        q = tmp
        while tmp is not None:
            q = q.next
            tmp.next = head
            head = tmp
            tmp = q
        return head
    
    def reverse(head: ListNode) -> ListNode:
        cur, pre = head, None
        while cur is not None:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
            # cur.next, pre, cur = pre, cur, cur.next
        return pre


if __name__ == '__main__':
    a = [1,2,3,4,5]
    l = ListNode(a[0])
    p = l
    for i in a[1:]:
        p.next = ListNode(i)
        p = p.next
    l1 = l
    while l1 is not None:
        print(l1.val,"->", end="")
        l1 = l1.next
    else:
        print(None)
    
    c = Solution()
    l2 = c.reverseList(l)
    while l2 is not None:
        print(l2.val,"->", end="")
        l2 = l2.next
    else:
        print(None)

        